package com.example.sorted;

/**
 * 直接插入排序
 * 1、基本描述：一种简单直观且具有稳定性能的排序算法。
 * 2、算法思路：
 * 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
 * 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），
 * 因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
 *
 * 比如：军训的列队，一般都要队形整齐，从低到高并列，假设此时从右边来了一个新兵蛋子想要加入列队，新兵蛋子比较慌神，在队前首先和最高的同学对视了一眼，高个同学发现自己比他高出一个头
 * 自动往右边横跨了一步为容纳新兵蛋子而腾出空间。新兵蛋子继续和下一个同学比较并腾出空间，
 * 当发现某个位置的同学和新兵的身高一样或者比新兵蛋子还矮，则新兵蛋子将插入上一个人腾出的这个位置，如此新兵蛋子找到了自己的位置了。
 *
 *
 * 实现步骤：
 * 若按递增有序的方式排列，对于已经排序的好的数列，从数列的最右边插入一个数值，该数值从右往左依次和已排序好的数列元素进行比较，
 * 将比较大的数列元素往后移动一个下标位置，
 *
 * 直接插入排序法在最好情况下（类似排兵），每趟排序只需作1次比较且不需要移动元素，因此N个元素排序时的总比较次数为N-1次。器时间复杂度为O（n*n），控件复杂度为O（1）。
 *
 *
 * @author wong
 * @Date: 2020-11-16
 * @Version: 1.0
 */
public class InsertSorted {


    public static void main(String[] args) {
        int[] array = {2, 3, 1, 5, 9, 2, 0, 4};

        /**
         * 第一轮
         * i = 0 , j = 1, array[0] < array[1] 不需要挪动位置 ---> 23159204
         * 第二轮
         * i= 1, j = 2 , array[1] > array[2] 需要挪动位置 1赋值给临时变量存储，并分别和3、2进行对比，2、3的下标分别往后挪移一位 ->> 123xxxx
         * ...
         */
        sorted(array);


        for (int a : array) {
            System.out.print(a);
        }
        System.out.println("");
    }


    /**
     * 自己实现的
     * @param array
     */
    private static void sorted(int array[]) {
        int j = 0, temp = 0;
        for (int i = 0; i < array.length - 1; i++) {
            temp = array[i + 1];
            System.out.println();
            for (j = i + 1; j > 0; j--) {
                if (temp < array[j - 1]) {
                    array[j] = array[j - 1];
                } else {
                    break;
                }
            }
            if (temp < array[j]) {
                array[j] = temp;
            }
        }

    }


    /**
     * 教程代码
     * @param array
     */
    private static void sorted2(int array[]) {

        int temp, j = 0;
        for (int i = 1; i < array.length; i++) {

            if (array[i] < array[i - 1]) {

                temp = array[i];
                array[i] = array[i - 1];

                for (j = i - 1; j > 0 && temp < array[j]; j--) {
                    array[j + 1] = array[j];
                }

                array[j + 1] = temp;
            }
        }
    }


}
